#include <gtest/gtest.h>
#include <vector>
#include <algorithm> // For sort
#include <utility> // For pair

using namespace ::std;

int cmp(pair<int, int> left, pair<int, int> right) {
	return left.second < right.second; // 升序排列
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
	vector<int> findIndex(vector<pair<int, int>>& mapper, int target);
	vector<int> makeAscendingOrder(int a, int b);
};

vector<int> Solution::twoSum(vector<int>& nums, int target) {
	int size = nums.size();
	vector<pair<int, int>> mapper;
	for(int i = 0; i < size; ++i) mapper.push_back(pair<int, int>(i, nums[i]));
	sort(mapper.begin(), mapper.end(), cmp);
	return findIndex(mapper, target);
}

vector<int> Solution::findIndex(vector<pair<int, int>>& mapper, int target) {
	int front = 0, end = mapper.size() - 1;
	for(; front < end; ++front) {
		int balance = target - mapper[front].second;
		while(front < end && balance < mapper[end].second) --end;
		if(balance == mapper[end].second) {
			return makeAscendingOrder(mapper[front].first, mapper[end].first);
		}
	}
	return {};
}

vector<int> Solution::makeAscendingOrder(int a, int b) {
	if(a < b) return {a, b};
	else return {b, a};
}

class TwoSumCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(TwoSumCheck, testTwoSum_1) {
	vector<int> nums = {10, 2, 3, 4, 5, 6};
	EXPECT_TRUE((vector<int>{1, 2}) == (solution.twoSum(nums, 5)));
}

TEST_F(TwoSumCheck, testTwoSum_2) {
	vector<int> nums({7, 2, 11, 15});
	EXPECT_TRUE(vector<int>({0, 1}) == solution.twoSum(nums, 9));
}

TEST_F(TwoSumCheck, testTwoSum_3) {
	vector<int> nums({3, 3, 4});
	EXPECT_TRUE(vector<int>({0, 1}) == solution.twoSum(nums, 6));
}

TEST_F(TwoSumCheck, testTwoSum_4) {
	vector<int> nums({0, 3, -3, 4, -1});
	EXPECT_TRUE(vector<int>({0, 4}) == solution.twoSum(nums, -1));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
